This invention relates to a multiprocessor computer system, and particularly, to a lock management scheme for shared resources.
A unit of processing (task) executed in a computer system uses various shared resources. In such as a, multiprocessor system, a plurality of tasks run concurrently and encounter contentions over the exclusive use of shared resources among the tasks. Therefore, lock management is required For example, when a plurality of tasks in an on-line system are running for the sales processing, these tasks make reference and revise the "current sales amount" in a common storage area individually. In this situation, when one task is making reference and revising the "current sales amount", other tasks must be inhibited from accessing the data.
Many of the prevalent computer systems have, a basic function of lock management and a hardware-based support of instruction which execute one-word reference-and-revision operations as unseparable operations, e.g., TEST AND SET instructions (TS instruction) and COMPARE AND SWAP instruction (CS instruction), as described in publication entitled "Computer Architecture and Parallel Processing", pp. 559-560, by K. Hwang and F. A. Briggs, published by McGraw Hill. However, a shared resource dealt with by lock management is not necessarily one word in the memory, and possibly it cannot be confined in one word as in the case of a disk-based data base.
Generally, lock management for the above-mentioned shared resources takes place as follows. The memory is provided, in addition to the areas for storing data of shared resources (numerous data A, B, C and so on of several K bytes each), a reference table, and one-word reference information (lock words) is stored in the table in correspondence to the shared data A, B, C and so on, so that the data are accessed for reference through the lock words.
The lock management for the data of shared resources can be accomplished by setting the exclusive-use (lock) flag in the lock word using the CS instruction or the like. At the beginning, the flag of the lock word is initialed (to 0 for example) so that it indicates that the shared resource is unlocked. A task which intends to lock the shared resource makes reference to the lock word using the CS instruction, and sets the flag to 1 if it is 0. On completion of exclusive use of the shared resource, the task resets the lock word to 0.
During the period when one processor makes reference to a lock word using the CS instruction, other processors are inhibited, on a hardware basis, to access to the lock word. Revision of a lock word fails unless it has been reset to 0. A task which has failed to revise the lock word, i.e., to lock the shared resource, using the CS instruction retries access repeatedly until it revises the lock word successfully In the following discussion, the acquisition of the right of using a shared resource exclusively will be termed "lock a resource", "have a lock of a resource", etc. The failure in locking a resource due to the exclusive use of it by another task will be termed "lock failure", "fail in lock acquisition", etc.
For the lock management in consideration of the retries in the case of lock failure, many prevalent computer systems employ the spin lock mechanism or wait/post mechanism, as described in JP-A-59-154563, JP-A-60128537, and JP-A-62-173535.
The spin lock mechanism is to repeat retries in a loop until the task locks the resource Namely, a task in need of a shared resource uses a processor exclusively and runs in a retry loop (spin loop) formed of a sequence of several instructions until it can lock the intended resource
The wait/post mechanism is also called the suspend/resume mechanism, block/activate mechanism, sleep/wakeup mechanism, etc., and it carries out the wait procedure to bring a lock-failing task into a wait state and then invoke the post procedure to restore the task to the ready state, thereby accomplishing the lock management. Namely, the system for the mutual exclusion control of shared resources comprises a wait procedure which, when a shared resource is locked by a task 1, brings a lock-failing task 2 into the wait state, and a post procedure which frees the task 2 from the wait state when the task 1 (or a task which has used the shared resource after the task 1) releases the resource.
In the following discussion, "running state" denotes that a task is in execution through the exclusive use of a processor, and "ready state" denotes that a task is waiting for an available processor, i.e., the task is ready to run as soon as any of processors in the system becomes available. "Wait state" denotes that a task cannot be executed on a processor until it becomes ready upon removal of the wait-causing event; for example, a task which has issued a wait macro because of failure in resource lock enters the wait state until it is posted. "Preempted state" is a sort of ready state, and it denotes that the execution is suspended due to an interrupt procedure or the like.
A task which has failed in resource lock transfers control to the wait procedure routine. The wait procedure routine places the lock-failing task in the wait procedure routine places the lock-failing task in wait state and invokes the dispatcher. The dispatcher dispatches another task in the ready state to a processor which has been executing a task that has entered the wait state. In case more than one ready task exists, the dispatcher selects a ready task for the processor depending on the predetermined priority-based schedule or dispatch algorithm.
Each task checks the presence of tasks in the wait state (waiting tasks) immediately before releasing (unlocking) the shared resource and, upon detecting a waiting task, transfers control to the post procedure routine. The post procedure routine restores the ready state of the waiting task. The restored task is thereafter dispatched by a processor by the dispatcher, and it locks a shared resource and resumes the processing.
In the following discussion, a task which initiates the post procedure will be termed a "post issue task" and a task which is rid of the wait state will be termed a "post receive task". The post issue task, post receive task and wait task are not particular tasks having these names. Instead, any task can become a post issue task or a post receive task in each occasion.